/*
 ============================================================================
 Name        : CLAN.c
 Author      : Linxiaozhi
 Version     :
 Copyright   : Your copyright notice
 Description : Hello World in C, Ansi-style
 ============================================================================
 */

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <stdarg.h>
#include "lang.h"
#define SELECTION 8
#if SELECTION==1
struct KP {
	unsigned int key :2;
	unsigned int :0;
	unsigned int password :2;
};
static FILE *fp;
void fun(int i) {
	printf("%d\n", i);
	fp = fopen("d:\\d.txt", "r");
}
typedef void (*pf)(int);
#define swap(t,x,y)   {t _t;\
		 _t = x; \
		x = y; \
		y = _t;}
int getInt(int *pn) {
	int ch, val = 0, sign = 0;
	while (isspace((ch = getc(fp))))
	;
	if (!isdigit(ch) && ch != EOF && ch != '-' && ch != '+')
	return 0;
	sign = ch == '-' ? -1 : 1;
	if (isdigit(ch))
	val = ch - '0';
	while (isdigit((ch = getc(fp)))) {
		val = 10 * val + (ch - '0');
	}
	if (ch != EOF)
	ungetc(ch, fp);
	val = sign * val;
	*pn = val;
	return ch;
}
int strlenL(char *s) {
	int n = 0;
	while (*s++ != '\0')
	n++;
	return n;
}
int main(void) {
	//	char cs[] = "1283";
	//	int num = atoiL(cs);
	//	printf("%d\n",num);

	//	char cs[] = "1283";
	//	reverse(cs);
	//	printf("%s\n",cs);

	//	char cs[100];
	//	itoaL(INT_MIN, cs);
	//	printf("%s\n", cs);
	//	itobL(432, cs,16);
	//	printf("%s\n", cs);
	//	itoa(432,cs,16);
	//	printf("%s\n", cs);
	//	itocL(432,cs,2);
	//	printf("%s\n", cs);

	//	char cs[100] = "safasd\tsdf\t";
	//	int in = trim(cs);
	//	printf("length:%d,%s", in, cs);

	//	char cs[100]="-124";
	//	double d =atof(cs);
	//	printf("%f\n",d);
	//	d =atofL(cs);
	//	printf("%f\n",d);
	//	char cs2[123]="-123.45e-3";
	//	d = atofeL(cs2);
	//	printf("%f\n",d);

	//	char cs[100]="213\n";
	//	trim(cs);
	//	printf("%s\n",cs);

	//	struct KP kp;
	//	kp.key = 7;
	//	printf("%d\n",kp.key);

	//	void fun(int);
	//	pf ppf=fun;
	//	ppf(4);

	//	system("notepad.exe");
	//	int * p = (int *)malloc(10*sizeof(int));
	//	*p++ = 3; *p++=5;
	////	int *q = (int *)realloc(p,10*sizeof(int));
	//	int *q = (int *)realloc(p,sizeof(int));
	//	if(q==NULL) return EXIT_FAILURE;
	//	printf("%d\n",q);

	//	char* string = malloc(100*sizeof(char));
	//	sprintf(string,"%s,%d","hello world",3);
	//	strcat(string,"hehe");
	//	printf("%s\n",string);
	//	free(string);
	//	fun(5);
	//if(fp!=NULL)
	//	printf("%d",fp->_charbuf);

	//	char aa[]="hello";
	//	printf("%d\n",sizeof(aa)/sizeof(char));

	//	int x = 12,y = 23;
	//	swap(int,x,y);
	//	printf("%d,%d\n",x,y);

	//	int array[10], n, num;
	//	fp = fopen("d:\\d.txt", "r");
	//	for (n = 0; n < 10 && getInt(&array[n]) != EOF; n++)
	//		;
	//	num = n;
	//	for (n = 0; n < num; n++)
	//		printf("%d\n", array[n]);

	//	char aa[] = "hello";
	//	printf("%d\n", strlenL(aa));
	//	printf("%d\n", strlen(aa));
	return EXIT_SUCCESS;
}
#elif SELECTION==2
#include "fileL.h"
#define MAXLINE 100
char pattern[] = "he";
//找出所有匹配的行
int main(void) {
	char line[MAXLINE];
	int found = 0;
	FILE *fp = fopen("d:\\d.txt", "r");
	while(getLine(line,MAXLINE,fp)>0) {
		if(strindexL(line,pattern)>=0) {
			printf("%s",line);
			found++;
		}
	}
	printf("\nnumber:%d",found);

	return EXIT_SUCCESS;
}
#elif SELECTION == 3
//计算器
#include "calc.h"

int main() {
	int type;
	double op2;
	char s[MAXOP];
	int var;
	FILE *fp = fopen("d:\\d.txt", "r");
	int i;
	double v;
	double val[26];
	double d;
	for (i = 0; i < 26; i++)
	val[i] = 0;

	while ((type = getTop(s, fp)) != EOF) {
		switch (type) {
			case NUMBER:
			push(atof(s));
			break;
			case '+':
			push(pop() + pop());
			break;
			case '-':
			op2 = pop();
			push(pop() - op2);
			break;
			case '*':
			push(pop() * pop());
			break;
			case '/':
			op2 = pop();
			if (op2 == 0) {
				printf("error!zero divisor!\n");
			} else {
				push(pop() / op2);
			}
			break;
			case '%':
			op2 = pop();
			if (op2 == 0) {
				printf("error!zero divisor!\n");
			} else {
				push(fmod(pop(), op2));
			}
			break;
			case '\n':
			v = pop();
			printf("%.8g\n", v);
			break;
			case '=':
			pop();
			if(isalpha(var)) {
				val[var - 'a'] = pop();
			}
			break;
			case NAME:
			if (strcmp(s, "sin") == 0) {
				push(sin(pop()));
			} else if (strcmp(s, "exp") == 0) {
				push(exp(pop()));
			} else if (strcmp(s, "pow") == 0) {
				op2 = pop();
				push(pow(pop(), op2));
			} else
			printf("error:unkown command %s", s);
			break;
			default:
			if (islower(type)) {
				var = type;
				push(val[type-'a']);
			} else if (type=='V') {
				push(v);
			} else
			printf("error:unkown command %s", s);

			break;
		}
	}

	return EXIT_SUCCESS;
}
#elif SELECTION == 4
#define ALLCOSIZE 1000
char allocbuffer[ALLCOSIZE];
char *pbase = allocbuffer;
char* alloc(int n) {
	if (pbase + n > allocbuffer + ALLCOSIZE) {
		printf("error.\n");
		return NULL;
	}
	pbase += n;
	return pbase - n;

}
void afree(char * p) {
	if (p >= allocbuffer && p <= allocbuffer + ALLCOSIZE)
	pbase = p;
}
int strlenL(char *p) {
	char * pl = p;
	while (*p != '\0')
	p++;
	return p - pl;
}
void strcpyL(char *s, char *t) {
	while (*s++ = *t++)
	;
}
int strcmpL2(char *s, char *t) {
	for (; *s == *t; s++, t++) {
		if (*s == '\0')
		return 0;
	}
	return *s - *t;
}
void strcatL2(char *s, char *t) {
	while (*s++)
	;
	s--;
	while (*s++ = *t++)
	;
}
int strend(char *s, char *t) {
	char *p = s;
	char *q = t;
	while (*p)
	p++;
	while (*q)
	q++;
	for (; *p == *q; p--, q--) {
		if (q == t || p == s)
		break;
	}
	if (*p == *q && q == t && *s != '\0')
	return 1;
	return 0;
}
void strcpynL(char *s, char *t, int n) {
	while (n-- > 0 && (*s++ = *t++) != '\0')
	;
	while (n-- > 0)
	*s++ = '\0';
}
int strcmpnL(char *s, char *t, int n) {
	for (; *s == *t; s++, t++) {
		if (*s == '\0' || --n <= 0)
		return 0;
	}
	return *s - *t;
}
int strindexL(char *s, char *t) {
	char *p, *q;
	for (; *s = '\0'; s++) {
		for (p = s, q = t; *q != '\0' && *p == *q; q++)
		;
	}
}
int main() {
	char* p = alloc(20);
	if (p == NULL)
	return EXIT_FAILURE;
	p[12] = 'a';
	printf("%d\n", p[18]);
	printf("%c\n", p[12]);
	afree(p);
	printf("%x\n", p[12]);
	p = alloc(50);
	strcpyL(p, "hello world");
	printf("%s\n", p);
	printf("%d\n", strlenL(p));
	printf("%d\n", strcmpL2(p, "hello hworld"));
	strcatL2(p, "c,cpp");
	printf("%s\n", p);
	printf("%d\n", strend(p, "c,cpdp"));
	strcpynL(p, "epklocsdisf", 6);
	printf("%s\n", p);
	printf("%d\n", strcmpnL(p, "epklocsdisf", 7));
	return EXIT_SUCCESS;
}
#elif SELECTION ==5
#define MAXLINES 5000
#define MAXLEN 1000
#define REVERSE  1
#define  NUMERIC  2
#define  FOLD  4
#define  DIR  8
FILE *fp;
char *lineptr[MAXLINES];

void swap(int left, int right) {
	char *temp = lineptr[left];
	lineptr[left] = lineptr[right];
	lineptr[right] = temp;
}

void qsortL(char *lineptr[], int left, int right) {
	if (left >= right)
	return;
	int temp = (left + right) / 2;
	int i = 0, j = left;
	swap(temp, left);
	for (i = left + 1; i <= right; i++) {
		if (strcmp(lineptr[i], lineptr[left]) < 0) {
			swap(++j, i);
		}
	}
	swap(left, j);
	qsortL(lineptr, left, j - 1);
	qsortL(lineptr, j + 1, right);

}
void qsortLR(char *[], int, int, int(*)(void *, void *));
void qsortLR(char *lineptr[], int left, int right, int(*cmp)(void *a, void *b)) {
	if (left >= right)
	return;
	int temp = (left + right) / 2;
	int i = 0, j = left;
	swap(temp, left);
	for (i = left + 1; i <= right; i++) {
		if ((*cmp)(lineptr[i], lineptr[left]) < 0) {
			swap(++j, i);
		}
	}
	swap(left, j);
	qsortLR(lineptr, left, j - 1, cmp);
	qsortLR(lineptr, j + 1, right, cmp);
}

int numcmp(char *a, char *b) {
	int i = atoi(a);
	int j = atoi(b);
	if (i > j)
	return 1;
	else if (i < j)
	return -1;
	else
	return 0;
}
extern int selection;
int charcmp(char *a, char *b) {
	char *p = a;
	char *q = b;
	char s, t;
	do {
		if (selection & DIR) {
			while (!isalnum(*p) && *p != ' ')
			p++;
			while (!isalnum(*q) && *q != ' ')
			q++;
		}
		s = selection & FOLD ? tolower(*p) : *p;
		p++;
		t = selection & FOLD ? tolower(*q) : *q;
		q++;

		if (s == t && s == '\0')
		return 0;
	}while (s == t);

	//	for (; towlower(*p) == tolower(*q); p++, q++) {
	//		if (*p == '\0')
	//			return 0;
	//	}
	return s - t;
}

int selection = 0;
int main(int argc, char* argv[]) {
	char p[MAXLEN];
	char *pp;
	int count = 0, len = 0, ch = 0;

	int(*fun)(void *a, void *b);

	fp = fopen("d:\\d.txt", "r");
	while (--argc > 0 && (*++argv)[0] == '-') {
		while (ch = *++argv[0]) {
			switch (ch) {
				case 'r':
				selection |= REVERSE;
				break;
				case 'n':
				selection |= NUMERIC;
				break;
				case 'f':
				selection |= FOLD;
				break;
				case 'd':
				selection |= DIR;
				break;
				default:
				break;
			}
		}
	}
	printf("%d\n",selection);
	while (fgets(p, MAXLEN, fp) != NULL) {
		len = strlen(p);
		pp = malloc((len + 1) * sizeof(char));
		if (!pp)
		return EXIT_FAILURE;
		strcpy(pp, p);
		lineptr[count++] = pp;
		printf("%s", pp);
	}
	printf("------------------------------------\n");
	if (selection & NUMERIC)
	fun = numcmp;
	else if (selection & FOLD)
	fun = charcmp;
	else
	fun = strcmp;
	qsortLR(lineptr, 0, count - 1, fun);

	if (selection & REVERSE)

	for (len = count - 1; len >= 0; len--) {
		printf("%s", lineptr[len]);
	}
	else
	for (len = 0; len < count; len++) {
		printf("%s", lineptr[len]);

	}

	return EXIT_SUCCESS;
}
#elif SELECTION == 6
#define MAXLEN 1000
int main(int argc, char* argv[]) {
	char p[MAXLEN];
	int ch;
	FILE *fp = fopen("d:\\d.txt", "r");
	int count = 0;
	int number = 0, except = 0;
	//	if (argc < 2)
	//		return EXIT_FAILURE;
	//
	//	if ((*++argv)[0] == '-')
	//		(*argv)++;
	//	if (**argv == 'n') {
	//		number = 1;
	//	} else if (**argv = 'x') {
	//		except = 1;
	//	}
	//	(*argv)++;
	//	if (**argv == 'x') {
	//		number = 1;
	//	} else if (**argv = 'n') {
	//		except = 1;
	//	}

	while (--argc > 0 && (*++argv)[0] == '-') {
		while (ch = *++argv[0]) {
			switch (ch) {
				case 'x':
				except = 1;
				break;
				case 'n':
				number = 1;
				break;
				default:
				break;
			}
		}

	}

	if (argc != 1) {
		printf("usage: find -x -n pattern\n");
		return EXIT_FAILURE;
	}

	while (fgets(p, MAXLEN, fp) != NULL) {
		if ((strstr(p, *argv) != NULL) != except) {
			if (number)
			printf("%d:", ++count);
			printf("%s", p);
		}
	}
	return EXIT_SUCCESS;
}
#elif SELECTION == 7
#include <stdlib.h>
struct key {
	char *word;
	int count;
};
struct key keytab[] = {"break", 0, "case", 0, "char", 0, "continue", 0, "default", 0, "void", 0, "if", 0, "while", 0,
	"int", 0, "define", 0, "include", 0, "for", 0,"return",0};
#define KEYS (sizeof(keytab)/sizeof(struct key))
#define MAXWORD 80
typedef struct key* keyLink;
int getWord(char *word, int limit, FILE *fp) {

	int ch;
	char *w = word;
	while (isspace(*w = ch = fgetc(fp)))
	;
	if (!isalnum(ch)) {
		*++w = '\0';
		return ch;
	}

	while (--limit > 0 && isalnum(*++w = ch = fgetc(fp)))
	;
	if (ch != EOF)
	fputc(ch, fp);
	*w = '\0';
	return word[0];
}
int binsearch(char *word, struct key tab[], int n) {
	int low = 0;
	int high = n - 1;
	int mid;
	while (low <= high) {
		mid = (low + high) / 2;
		int result = strcmp(word, tab[mid].word);
		if (result == 0)
		return mid;
		else if (result < 0)
		high = mid - 1;
		else
		low = mid + 1;
	}
	return -1;
}
keyLink binsearchLink(char *word, struct key tab[], int n) {
	keyLink low = &tab[0];
	keyLink high = &tab[n];
	keyLink mid;
	while (low < high) {
		mid = low + (high - low) / 2;
		int result = strcmp(word, mid->word);
		if (result == 0)
		return mid;
		else if (result < 0)
		high = mid;
		else
		low = mid + 1;
	}
	return NULL;
}
int structCmp(struct key *a, struct key *b) {
	return strcmp(a->word, b->word);
}

int main(int argc, char* argv[]) {
	char word[MAXWORD];
	int n;
	FILE *fp = fopen("d:\\d.txt", "r");
	keyLink link;
	if (fp == NULL)
	return EXIT_FAILURE;
	int (*fun)(void *, void *);
	fun = structCmp;

	qsort(keytab, KEYS, sizeof(struct key), fun);

	while (getWord(word, MAXWORD, fp) > 0) {
		if (isalpha(word[0]))
		if ((link = binsearchLink(word, keytab, KEYS)) != NULL) {
			link->count++;
		}
	}

	//	for (n = 0; n < KEYS; n++) {
	//		printf("word:%s,count:%d\n", keytab[n].word, keytab[n].count);
	//	}
	link = keytab;
	for (; link < keytab + KEYS; link++) {
		printf("word:%s,count:%d\n", link->word, link->count);
	}

	return EXIT_SUCCESS;
}
#elif SELECTION==8

#define MAXWORD 80
#include "hash.h"
typedef struct linklist* llink;
struct linklist {
	int lnum;
	llink next;
};

typedef struct tnode* tlink;
struct tnode {
	char *word;
	int count;
	tlink left;
	tlink right;
	llink lines;
};
int fch = -2;
int getchL(FILE *fp) {
	int in;
	if (fch == -2)
		return fgetc(fp);
	else {
		in = fch;
		fch = -2;
		return in;
	}
}

void ungetchL(int ch) {
	fch = ch;
}
int getWord(char *word, int limit, FILE *fp) {

	int ch;
	char *w = word;
	while (isspace(*w = ch = getchL(fp)) && ch != '\n')
		;

	if (!isalnum(ch)) {
		*++w = '\0';
		return ch;
	}

	while (--limit > 0 && isalnum(*++w = ch = fgetc(fp)))
		;
	if (ch != EOF)
		ungetchL(ch);
	*w = '\0';
	return word[0];
}
extern int nline;
tlink addtree(tlink root, char *word) {
	char *p;
	int ch;
	if (root == NULL) {
		root = (struct tnode*) (malloc(sizeof(struct tnode)));
		p = malloc(strlen(word) + 1);
		if (p != NULL)
			strcpy(p, word);
		root->word = p;
		root->count = 1;
		root->left = NULL;
		root->right = NULL;
		//head
		struct linklist* node = (struct linklist*) (malloc(sizeof(struct linklist)));
		node->next = NULL;
		node->lnum = -1;
		root->lines = node;
		//first node
		node = (struct linklist*) (malloc(sizeof(struct linklist)));
		node->next = NULL;
		node->lnum = nline;
		root->lines->next = node;

	} else {
		if ((ch = strcmp(word, root->word)) == 0) {
			root->count++;

			llink pre = root->lines;
			for (; pre->next != NULL && pre->next->lnum != nline; pre = pre->next)
				;

			if (pre->next == NULL) {
				struct linklist
						* node =
								(struct linklist*) (malloc(
										sizeof(struct linklist)));
				node->next = NULL;
				node->lnum = nline;
				pre->next = node;
				//root->count++;
			}

		} else if (ch < 0)
			root->left = addtree(root->left, word);
		else
			root->right = addtree(root->right, word);
	}

	return root;
}
int tcount = 0;
#define TMAX  200
tlink tlinks[TMAX];
void treestore(tlink root) {
	if (root) {
		treestore(root->left);
		if (tcount < TMAX)
			tlinks[tcount++] = root;
		treestore(root->right);
	}
}
int tlinkcmp(tlink a, tlink b) {
	if (a->count < b->count)
		return -1;
	else if (a->count > b->count)
		return 1;
	else
		return 0;
}
void treesort() {
	int gap, i, j;
	tlink temp;
	for (gap = tcount / 2; gap > 0; gap /= 2) {
		for (i = gap; i < tcount; i++) {
			for (j = i - gap; j >= 0; j -= gap) {
				if (tlinkcmp(tlinks[j], tlinks[j + gap]) >= 0)
					break;
				temp = tlinks[j];
				tlinks[j] = tlinks[j + gap];
				tlinks[j + gap] = temp;
			}
		}
	}
}
void treeprint(tlink root) {
	if (root) {
		treeprint(root->left);
		printf("word:%s,count:%d;", root->word, root->count);
		llink ptr = root->lines;
		while (ptr->next) {
			printf(" %d ", ptr->next->lnum);
			ptr = ptr->next;
		}
		printf("\n");
		treeprint(root->right);
	}
}
char *nw[] = { "for", "if", "int" };
int noiseword(char *word) {
	int cond, low = 0, high = sizeof(nw) / sizeof(char *) - 1, mid;
	while (low <= high) {
		mid = (low + high) / 2;
		cond = strcmp(word, nw[mid]);
		if (cond == 0)
			return mid;
		else if (cond < 0)
			high = mid - 1;
		else
			low = mid + 1;
	}
	return -1;
}
int nline = 1;
int main(int argc, char* argv[]) {
	char word[MAXWORD];
	char * name;
	char *defn;
	int start = 0;
	int n = (--argc && (*++argv)[0] == '-') ? atoi(++argv[0]) : 6;

	tlink root = NULL;
	nlistlink nlink;
	FILE *fp = fopen("d:\\d.txt", "r");
	//printf("n:%d\n", n);
	if (fp == NULL)
		return EXIT_FAILURE;

	while (getWord(word, MAXWORD, fp) >= 0) {
		//printf("%s\n",word);
		if (isalpha(word[0]) && noiseword(word) < 0) {
			root = addtree(root, word);
		} else if (word[0] == '\n') {
			nline++;
		} else if (word[0] == '#') {
			start = 1;
			continue;
		}

		if (start == 1) {
			if (strcmp(word, "define") == 0) {
				start = 2;
				continue;
			} else {
				start = 1;
				continue;
			}
		} else if (start == 2) {
			name = malloc(strlen(word) + 1);
			strcpy(name, word);
			start = 3;
			continue;
		} else if (start == 3) {
			defn = malloc(strlen(word) + 1);
			strcpy(defn, word);
			install(name, defn);
			free(name);
			free(defn);
			start = 1;
		}
	}

	printf("line:%d\n", nline);
	//treeprint(root);

	treestore(root);
	treesort();

	for (n = 0; n < tcount; n++) {
		root = tlinks[n];
		printf("word:%s,count:%d;", root->word, root->count);
		llink ptr = root->lines;
		while (ptr->next) {
			printf(" %d ", ptr->next->lnum);
			ptr = ptr->next;
		}
		printf("\n");
	}
	printf("------------------------\n");

	extern nlistlink hashtab[HASHSIZE];
	for (n = 0; n < HASHSIZE; n++) {
		nlink = hashtab[n];
		for (; nlink; nlink = nlink->next) {
			printf("%s,%s\n", nlink->name, nlink->defn);
		}
	}
	return EXIT_SUCCESS;
}
#endif
